/*给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
fun main() {
//    val intArray = intArrayOf(0, 1, 2, 2, 3, 0, 4, 2)
//    val intArray = intArrayOf(1)
//    val intArray = intArrayOf(3, 2, 2, 3)
//    val intArray = intArrayOf(3, 3)
    val intArray = intArrayOf(2, 2, 3)
//    val intArray = intArrayOf(4, 2, 0, 2, 2, 1, 4, 4, 1, 4, 3, 2)
//    val intArray = intArrayOf(4,4,0,1,0,2)
//    println(e2(intArray, 0))
//    println(e2(intArray, 4))
//    println(e2(intArray, 3))
//    println(e2(intArray, 2))
//    println(answer(intArray, 3))
    println(answer2(intArray, 3))
    println(intArray.contentToString())
}

//3,2,2,3
//3223,(f1)2323,（f2）2233，f(3)2233,f(4)2233
//这个答案的思路就是循环，slow获取一个，fast获取下一个，如果slow是需要移除的则执行（1），否则执行（2）
// （1）如果slow和fast相同，fast+1，然后判断fast是否为需要移除的数，是的话就+1找下一个，不是的话就和slow交换位置,如果fast大于等于数组大小则结束
// （2）slow+1，fast等于slow
fun answer(nums: IntArray, `val`: Int): Int {
    var slow = 0
    var fast = 0
    while (slow < nums.size) {
        println("slow:$slow,fast:$fast")
        println(nums.contentToString())
        if (nums[slow] == `val`) {
            if (slow == fast) {
                fast++
            } else {
                if (fast >= nums.size) {
                    slow--
                    break
                }
                if (nums[fast] == `val`) {
                    fast++
                } else {
                    nums[slow] = nums[fast]
                    nums[fast] = `val`
                }
            }
        } else {
            slow++
            fast = slow
        }
    }
    return slow + 1
}

//3,2,2,3
//3223,2223，2223
//2,2,3
//3,3,3,2
fun answer2(nums: IntArray, `val`: Int): Int {//双指针法（快慢指针法）
    var pos = 0
//    nums.forEachIndexed { index, i ->
//        if (i != `val`) {
//            val p = nums[pos]
//            nums[pos++] = i
//            nums[index] = p
//        }
//        println(pos)
//        println(nums.contentToString())
//    }
    nums.forEach { i ->//高性能做法，不考虑替换双方，只替换一个，并用pos记录替换的位置
        if (i != `val`) {
            nums[pos++] = i
        }
        println(pos)
        println(nums.contentToString())
    }
    return pos
}

//Test1
//1,2,2,3,4 (2)
//1,2,2,3,4->1,3,2,2,4->1,3,4,2,2
//Test2
//0,1,2,2,3,0,4,2(2)
//0,1,2,2,3,0,4,2[2]->0,1,3,2,2,0,4,2[3]->0,1,3,0,2,2,4,2[4]->0,1,3,0,4,2,2,2
//Test3
//3,3(3)
//Test4
//3,2,2,3(3)
//3,2,2,3->2,2,3,3
//3,2,2,3->3,3,2,3->3,3,3,3
//Test5
//[4,2,0,2,2,1,4,4,1,4,3,2](4)
//
//
fun e2(nums: IntArray, `val`: Int): Int {
    val size = nums.size
    if (size == 1) {
        return if (nums[0] == `val`) 0
        else 1
    }
    var max = 0
    var remove = 0
    for (num in nums) {
        if (num > max) max = num
    }
    nums.forEachIndexed { index, i ->
        if (i == `val`) {
            if (index + 1 == size) {
                remove++
                println("index + 1 == size:$remove")
            } else {
                for (i2 in size - 1 downTo index + 1) {
                    val i1 = nums[i2]
                    if (i2 - index != 1 && i1 == max) {
                        continue
                    }
                    if (i1 != `val`) {
                        nums[index] = i1
                        nums[i2] = max
                        remove++
                        println("i1 != `val`:$remove")
                        break
                    } else if (i2 - index == 1) {
                        remove++
                        println("i1 == `val`:$remove")
                        break
                    }
                }
            }
        }
        println(nums.contentToString())
    }
    return size - remove
}